from typing import List

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        """
        使用动态规划解决一和零问题
        
        Args:
            strs: 二进制字符串数组
            m: 最多0的个数
            n: 最多1的个数
            
        Returns:
            最大子集的长度
        """
        # dp[i][j] 表示使用最多i个0和j个1能组成的最大子集长度
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        for s in strs:
            # 统计当前字符串中0和1的个数
            zeros = s.count('0')
            ones = s.count('1')
            
            # 从后往前遍历，避免重复使用
            for i in range(m, zeros - 1, -1):
                for j in range(n, ones - 1, -1):
                    # 状态转移方程：选择当前字符串或不选择
                    dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)
        
        return dp[m][n]
    
    def findMaxFormOptimized(self, strs: List[str], m: int, n: int) -> int:
        """
        优化版本：预处理字符串统计
        """
        # 预处理：统计每个字符串的0和1的个数
        counts = []
        for s in strs:
            zeros = s.count('0')
            ones = s.count('1')
            counts.append((zeros, ones))
        
        # 动态规划
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        for zeros, ones in counts:
            for i in range(m, zeros - 1, -1):
                for j in range(n, ones - 1, -1):
                    dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)
        
        return dp[m][n]

def count_zeros_ones(s: str) -> tuple:
    """辅助函数：统计字符串中0和1的个数"""
    zeros = s.count('0')
    ones = len(s) - zeros
    return zeros, ones
